package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		head := queue[0]
		queue = queue[1:]
		if head != nil {
			head.Left, head.Right = head.Right, head.Left
		}
		if head != nil {
			queue = append(queue, head.Left)
			queue = append(queue, head.Right)
		}
	}
	return root
}

func main() {

}
